{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Size Subarray in Infinite Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSizeSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无限数组的最短子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>nums</code> 和一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>下标从 <strong>0</strong> 开始的数组 <code>infinite_nums</code> 是通过无限地将 nums 的元素追加到自己之后生成的。</p>\n",
    "\n",
    "<p>请你从 <code>infinite_nums</code> 中找出满足 <strong>元素和</strong> 等于&nbsp;<code>target</code> 的 <strong>最短</strong> 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], target = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在这个例子中 infinite_nums = [1,2,3,1,2,3,1,2,...] 。\n",
    "区间 [1,2] 内的子数组的元素和等于 target = 5 ，且长度 length = 2 。\n",
    "可以证明，当元素和等于目标值 target = 5 时，2 是子数组的最短长度。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,2,3], target = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在这个例子中 infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].\n",
    "区间 [4,5] 内的子数组的元素和等于 target = 4 ，且长度 length = 2 。\n",
    "可以证明，当元素和等于目标值 target = 4 时，2 是子数组的最短长度。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,6,8], target = 3\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>在这个例子中 infinite_nums = [2,4,6,8,2,4,6,8,...] 。\n",
    "可以证明，不存在元素和等于目标值 target = 3 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-size-subarray-in-infinite-array](https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-size-subarray-in-infinite-array](https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n5', '[1,1,1,2,3]\\n4', '[2,4,6,8]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        tot = sum(nums)\n",
    "        \n",
    "        a, b = divmod(target, tot)\n",
    "        \n",
    "        if b == 0:\n",
    "            return n * a\n",
    "        \n",
    "        ans = float('inf')\n",
    "        nums *= 2\n",
    "        \n",
    "        i = tmp = 0\n",
    "        for j in range(len(nums)):\n",
    "            tmp += nums[j]\n",
    "            while i < j and tmp > b:\n",
    "                tmp -= nums[i]\n",
    "                i += 1\n",
    "            if tmp == b:\n",
    "                ans = min(ans, j - i + 1)\n",
    "        \n",
    "        return ans + n * a if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        total = sum(nums)\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        left = 0\n",
    "        s = 0\n",
    "\n",
    "        for right in range(n*2):\n",
    "            s += nums[right%n]\n",
    "            while s > target % total:\n",
    "                s -= nums[left%n]\n",
    "                left += 1\n",
    "            if s == target%total:\n",
    "                ans = min(ans,right-left+1)\n",
    "        if ans == inf:\n",
    "            return -1\n",
    "        return ans + target // total * n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        total = sum(nums)\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        left = s = 0\n",
    "        for right in range(n * 2):\n",
    "            s += nums[right % n]\n",
    "            while s > target % total:\n",
    "                s -= nums[left % n]\n",
    "                left += 1\n",
    "            if s == target % total:\n",
    "                ans = min(ans, right - left + 1)\n",
    "        return ans + target // total * n if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        s, n = sum(nums), len(nums)\n",
    "        t = target % s\n",
    "        left = right = 0\n",
    "        ans = inf\n",
    "        sm = 0\n",
    "        while right < 2 * n:\n",
    "            while right < 2 * n and sm < t:\n",
    "                sm += nums[right % n]\n",
    "                right += 1\n",
    "            if sm == t:\n",
    "                ans = min(ans, right - left)\n",
    "            sm -= nums[left % n]\n",
    "            left += 1\n",
    "        return -1 if ans == inf else ans + target // s * n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=sum(nums)\n",
    "        z=target//s\n",
    "        t=target%s\n",
    "        if t==0: return n*z\n",
    "        newn=nums+nums\n",
    "        ans=0\n",
    "        l=0\n",
    "        res=inf\n",
    "        for r in range(n*2):\n",
    "            ans+=newn[r]\n",
    "            while ans>t:\n",
    "                ans-=newn[l]\n",
    "                l+=1\n",
    "            if t==ans:\n",
    "                res=min(res,r-l+1)\n",
    "\n",
    "        if res==inf: return -1\n",
    "        else:\n",
    "            return res+z*n\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        s=sum(nums)\n",
    "        t2=target%s\n",
    "        res=target//s\n",
    "        n=len(nums)\n",
    "        newns=nums+nums\n",
    "        ans=inf\n",
    "        left=s=0\n",
    "        for right in range(2*n):\n",
    "            s+=newns[right]\n",
    "            while s>t2:\n",
    "                s-=newns[left]\n",
    "                left+=1\n",
    "            if s==t2:\n",
    "                ans=min(ans,right-left+1)\n",
    "        return ans+n*res if ans<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], t: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if t in nums: return 1\n",
    "        if t < min(nums): return -1\n",
    "\n",
    "        def f(a, t):\n",
    "            n = len(a)\n",
    "            tmp = 0\n",
    "            r = -1\n",
    "            ans = inf\n",
    "            for l in range(n):\n",
    "                while r + 1 < n and tmp < t:\n",
    "                    r += 1\n",
    "                    tmp += a[r]\n",
    "                if tmp == t:\n",
    "                    ans = min(ans, r - l + 1)\n",
    "                tmp -= a[l]\n",
    "            return ans\n",
    "\n",
    "\n",
    "        x = t // s\n",
    "        a = nums * 8\n",
    "        if x > 5:\n",
    "            t -= (x - 2) * s\n",
    "            ans = f(a, t)\n",
    "            if ans == inf:\n",
    "                return -1\n",
    "            return ans + (x - 2) * n\n",
    "\n",
    "        ans = f(a, t)\n",
    "        return ans if ans != inf else -1\n",
    "        \n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        t = target\n",
    "        prefix = [0]\n",
    "        for i in nums:\n",
    "            prefix.append(prefix[-1]+i)\n",
    "        # print(prefix[-1])\n",
    "        target %= prefix[-1]\n",
    "        ans += (t - target)/prefix[-1]*len(nums)\n",
    "        if target == 0: return int(ans)\n",
    "        tmp = ans\n",
    "        \n",
    "        nums = nums+nums\n",
    "        # print(nums)\n",
    "        \n",
    "        sum = 0\n",
    "        left = 0\n",
    "        flag = 0\n",
    "        for right in range(len(nums)):\n",
    "            sum += nums[right]\n",
    "            while sum > target:\n",
    "                sum -= nums[left]\n",
    "                left += 1\n",
    "            if sum == target:\n",
    "                ans = min(ans, tmp + right - left + 1) if flag else tmp + right - left + 1\n",
    "                flag = 1\n",
    "                # print(tmp + right - left + 1, ans)\n",
    "                    \n",
    "        return int(ans) if flag else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [0] * (2*n+1)\n",
    "        for i in range(1, 2*n+1):\n",
    "            prefix[i] = prefix[i-1] + nums[(i-1) % n]\n",
    "        \n",
    "        total = sum(nums)\n",
    "        ans = float('inf')\n",
    "        left = 0\n",
    "\n",
    "        for right in range(1, 2*n + 1):\n",
    "            while prefix[right] - prefix[left] > target % total:\n",
    "                left += 1\n",
    "            if prefix[right] - prefix[left] == target % total:\n",
    "                ans = min(ans, right - left)\n",
    "                \n",
    "        return ans + target // total * n if ans < float('inf') else -1\n",
    "\n",
    "\n",
    "'''\n",
    "元素和等于target的最短子数组\n",
    "目标：\n",
    " - 子序列的和是target\n",
    " - 子序列的长度最短\n",
    "\n",
    "\n",
    "长度是4\n",
    "idx 0 1 2 3 4 5 6 7 8 9\n",
    "rdx 0 1 2 3 0 \n",
    "\n",
    "rdx = idx % 4\n",
    "\n",
    "原始\n",
    "[2,1,5,7,7,1,6,3]\n",
    "两倍\n",
    "[2,1,5,7,7,1,6,3,2,1,5,7,7,1,6,3]\n",
    "\n",
    "动态计算前缀和\n",
    "\n",
    "不断累加前缀和，如果当前的前缀和-k出现在字典当中，则计算长度，取最小长度\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        temp=0\n",
    "        n=len(nums)\n",
    "        pre=[]\n",
    "        for i in range(n):\n",
    "            temp+=nums[i]\n",
    "            pre.append(temp)\n",
    "        total=pre[n-1]\n",
    "        for i in range(n):\n",
    "            temp+=nums[i]\n",
    "            pre.append(temp)\n",
    "            \n",
    "        res=1e10\n",
    "        for i in range(n):\n",
    "            ans=0\n",
    "            diff=target\n",
    "            ans+=n*(diff//total)\n",
    "            diff%=total\n",
    "            \n",
    "            if diff==0:\n",
    "                return ans\n",
    "            \n",
    "            \n",
    "            left=i\n",
    "            right=2*n-1\n",
    "            temp=2*n\n",
    "            while left<right:\n",
    "                mid=(left+right)>>1\n",
    "                if pre[mid]-pre[i]+nums[i]<diff:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid\n",
    "            if pre[right]-pre[i]+nums[i]==diff:\n",
    "                ans+=right-i+1\n",
    "                res=min(res,ans)\n",
    "        # print(total)\n",
    "        return res if res!=1e10 else -1\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n,sumn=len(nums),sum(nums)\n",
    "        ans=10000000000\n",
    "        if(target<sumn):\n",
    "            q,sumq=0,0\n",
    "            for i in range(n):\n",
    "                if(i):sumq-=nums[i-1]\n",
    "                while(q<n and sumq<target):sumq+=nums[q];q+=1\n",
    "                if(sumq==target):ans=min(ans,q-i)\n",
    "        ntar=target%sumn\n",
    "        if(ntar==0):return n*(target//sumn)\n",
    "        l,r=[0]*n,[0]*n;l[0],r[-1]=nums[0],nums[-1]\n",
    "        for i in range(1,n):l[i]=l[i-1]+nums[i]\n",
    "        for i in range(n-2,-1,-1):r[i]=r[i+1]+nums[i]\n",
    "        for i in range(n):\n",
    "            if(l[i]==ntar):ans=min(ans,n*(target//sumn)+i+1)\n",
    "            if(r[i]==ntar):ans=min(ans,n*(target//sumn)+n-i)\n",
    "        le,re=0,0\n",
    "        while(re<n and l[le]+r[re]>ntar):re+=1\n",
    "        if(re<n and l[le]+r[re]==ntar):ans=min(ans,n*(target//sumn)+le+1+n-re)\n",
    "        while(le+1<n and re<n):\n",
    "            le+=1\n",
    "            while(re<n and l[le]+r[re]>ntar):re+=1\n",
    "            if(re<n and l[le]+r[re]==ntar):ans=min(ans,n*(target//sumn)+le+1+n-re)\n",
    "        if(target>sumn):ntar+=sumn\n",
    "        else:return ans if ans<=target else -1\n",
    "        le,re=0,0\n",
    "        while(le<n and l[le]+r[re]<ntar):le+=1\n",
    "        if(le<n and l[le]+r[re]==ntar):ans=min(ans,n*(target//sumn-1)+le+1+n-re)\n",
    "        while(re<n and l[le]+r[re]>ntar):re+=1\n",
    "        if(re<n and l[le]+r[re]==ntar):ans=min(ans,n*(target//sumn-1)+le+1+n-re)\n",
    "        while(le+1<n and re<n):\n",
    "            le+=1\n",
    "            while(re<n and l[le]+r[re]>ntar):re+=1\n",
    "            if(re<n and l[le]+r[re]==ntar):ans=min(ans,n*(target//sumn-1)+le+1+n-re)\n",
    "        return ans if ans<=target else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1.子数组和，即区间和，利用前缀和\n",
    "# 2.在前缀和数组中，寻找两数之差等于target且两数位置间距最小，可以利用滑动窗口\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=sum(nums)\n",
    "        cnt=((target+s-1)//s+1)*n\n",
    "        prefixSum=[0]\n",
    "        # 计算前缀和\n",
    "        for i in range(cnt):\n",
    "            prefixSum.append(prefixSum[i]+nums[int(i%n)])\n",
    "        # 滑动窗口，找最短距离的两个数之差等于target\n",
    "        i,j=0,1\n",
    "        ans=-1\n",
    "        while j<(cnt+1) and i<=j:\n",
    "            if prefixSum[j]-prefixSum[i]<target:\n",
    "                j+=1\n",
    "            elif prefixSum[j]-prefixSum[i]==target:\n",
    "                if ans==-1:\n",
    "                    ans=j-i\n",
    "                else:\n",
    "                    ans=min(ans,j-i)\n",
    "                j+=1\n",
    "                i+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ans\n",
    "\n",
    "#   1 2 3  1 2 3   1   2   3   1   2   3\n",
    "# 0 1 3 6  7 9 12  13  15  18  19  21  24\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=sum(nums)\n",
    "        cnt=2*n\n",
    "        prefixSum=[0]\n",
    "        k=target%s\n",
    "        # 计算前缀和\n",
    "        for i in range(cnt):\n",
    "            prefixSum.append(prefixSum[i]+nums[int(i%n)])\n",
    "        # 滑动窗口，找最短距离的两个数之差等于target\n",
    "        i,j=0,1\n",
    "        ans=-1\n",
    "        while j<(cnt+1) and i<=j:\n",
    "            if prefixSum[j]-prefixSum[i]<k:\n",
    "                j+=1\n",
    "            elif prefixSum[j]-prefixSum[i]==k:\n",
    "                if ans==-1:\n",
    "                    ans=j-i\n",
    "                else:\n",
    "                    ans=min(ans,j-i)\n",
    "                j+=1\n",
    "                i+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ans+target//s*n if ans!=-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=sum(nums)\n",
    "        a=target//s\n",
    "        b=target%s\n",
    "        num=nums+nums\n",
    "        sm=[0]+list(accumulate(num))\n",
    "        def binary_search(l,v):\n",
    "            left=0\n",
    "            right=len(l)-1\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if l[mid]==v:\n",
    "                    return mid\n",
    "                elif l[mid]>v:\n",
    "                    right=mid-1\n",
    "                else:\n",
    "                    left=mid+1\n",
    "            else:\n",
    "                return -1\n",
    "        ans=inf\n",
    "        for i in range(len(sm)):\n",
    "            c=binary_search(sm,b+sm[i])\n",
    "            if c!=-1:\n",
    "                ans=min(ans,c-i)\n",
    "        if ans==inf:\n",
    "            return -1\n",
    "        return n*a+ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        def gets(stidx):\n",
    "            nonlocal n,target\n",
    "            l,r = stidx,2*n\n",
    "            while l<r:\n",
    "                mid = l+r>>1\n",
    "                if pre[mid]-pre[stidx-1]>=yu:\n",
    "                    r = mid\n",
    "                else: l = mid+1\n",
    "            \n",
    "            return l\n",
    "        \n",
    "        n = len(nums)\n",
    "        sums = sum(nums)\n",
    "        res = 1<<31\n",
    "\n",
    "        cnt = target//sums\n",
    "        yu = target-cnt*sums\n",
    "        if yu==0:\n",
    "            return cnt*n\n",
    "        a = [0]+nums+nums\n",
    "        pre = [0]*(2*n+10)\n",
    "        for i in range(1,2*n+1):\n",
    "            pre[i] = pre[i-1]+a[i]\n",
    "\n",
    "        for i in range(1,2*n+1):\n",
    "\n",
    "            r = gets(i)\n",
    "            if pre[r]-pre[i-1]==yu:\n",
    "                res = min(res,r-i+1+cnt*n)\n",
    "\n",
    "        if res==1<<31: res = -1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        cumsum = [0]\n",
    "        for num in nums:\n",
    "            cumsum.append(cumsum[-1] + num)\n",
    "        plus = (target // cumsum[-1]) * n\n",
    "        target %= cumsum[-1]\n",
    "        for num in nums:\n",
    "            cumsum.append(cumsum[-1] + num)\n",
    "        \n",
    "        print(cumsum)\n",
    "        res = int(1e9)\n",
    "        for i in range(n):\n",
    "            k = cumsum[i] + target\n",
    "            j = bisect_left(cumsum, k, i)\n",
    "            if j < len(cumsum) and cumsum[j] == k:\n",
    "                res = min(res, j - i)\n",
    "        if res == int(1e9):\n",
    "            res = -1\n",
    "            plus = 0\n",
    "                \n",
    "        return res + plus\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        a = 0\n",
    "        if target > s:\n",
    "            a = n * (target // s)\n",
    "            target -= target // s * s\n",
    "        if target == s:\n",
    "            return n\n",
    "        pos = {0: -1}\n",
    "        pre = 0\n",
    "        b = inf\n",
    "        for i, x in enumerate(nums):\n",
    "            pre += x\n",
    "            if (t := pre - target) in pos:\n",
    "                b = min(b, i - pos[t])\n",
    "            if (t := pre - (s - target)) in pos:\n",
    "                b = min(b, n - (i - pos[t]))\n",
    "            pos[pre] = i\n",
    "        return -1 if b == inf else a + b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (2*n+1)\n",
    "        array = nums + nums\n",
    "        for i in range(1,2*n+1):\n",
    "            prefix_sum[i] = array[i-1] + prefix_sum[i-1]\n",
    "        mods = target % prefix_sum[n]\n",
    "        k = target // prefix_sum[n]\n",
    "        i, j = 0, 1\n",
    "        min_length = None\n",
    "        print(prefix_sum)\n",
    "        while i<= j and j<=2*n:\n",
    "            sums = prefix_sum[j] - prefix_sum[i]\n",
    "            if sums < mods:\n",
    "                j +=1\n",
    "            elif sums == mods:\n",
    "                length = j - i\n",
    "                if min_length == None:\n",
    "                    min_length = length\n",
    "                elif min_length > length:\n",
    "                    min_length = length\n",
    "                i +=1\n",
    "            elif sums > mods:\n",
    "                i += 1\n",
    "        if min_length == None:\n",
    "            return -1\n",
    "        min_length = k* n + min_length\n",
    "        return min_length\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        cumsum = list(accumulate(nums, initial=0))\n",
    "        summ = cumsum[-1]\n",
    "        loc = {a: i for i, a in enumerate(cumsum)}\n",
    "        q, r = divmod(target, summ)\n",
    "        if r == 0:\n",
    "            return n * q\n",
    "        \n",
    "        ans = maxsize\n",
    "        # 当r != 0时，寻找nums的一个和为r或(summ - r)的子数组\n",
    "        for i in range(n):\n",
    "            if cumsum[i] + r in loc:\n",
    "                ans = min(ans, n * q + loc[cumsum[i] + r] - i)\n",
    "            if cumsum[i] + summ - r in loc:\n",
    "                ans = min(ans, n * q + n - (loc[cumsum[i] + summ - r] - i))\n",
    "        return ans if ans < maxsize else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        sum_all = sum(nums)\n",
    "        loops = target // sum_all\n",
    "        res = target % sum_all\n",
    "        \n",
    "        # 拆成两个问题，\n",
    "        # 1. 查找nums中最短的长为res的子数组\n",
    "        pre_sum = 0\n",
    "        pre_hash = {0: -1}\n",
    "        ans_len_1 = inf\n",
    "        for i in range(n):\n",
    "            if pre_sum - res + nums[i] in pre_hash:\n",
    "                ans_len_1 = min(i - pre_hash[pre_sum - res + nums[i]], ans_len_1)\n",
    "            pre_sum += nums[i]\n",
    "            pre_hash[pre_sum] = i\n",
    "            \n",
    "        # 2. 查找nums中最长的长为sum_all-res的子数组\n",
    "        pre_sum = 0\n",
    "        pre_hash = {0: -1}\n",
    "        ans_len_2 = 0\n",
    "        for i in range(n):\n",
    "            if pre_sum - (sum_all - res) + nums[i] in pre_hash:\n",
    "                ans_len_2 = max(i - pre_hash[pre_sum - (sum_all - res) + nums[i]], ans_len_2)\n",
    "            pre_sum += nums[i]\n",
    "            if pre_sum not in pre_hash:\n",
    "                pre_hash[pre_sum] = i\n",
    "        \n",
    "        if ans_len_1 == inf and ans_len_2 == 0:\n",
    "            return -1\n",
    "        ans_len = min(ans_len_1, n - ans_len_2)\n",
    "        return loops * n + ans_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if target in nums:\n",
    "            return 1\n",
    "        f = True\n",
    "        if max(nums)>target:\n",
    "            f = False\n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + nums[i]\n",
    "        pre.pop(0)\n",
    "        if not f:\n",
    "            m = {0:-1}\n",
    "            for i,x in enumerate(pre):\n",
    "                if x not in m:\n",
    "                    m[x] = i\n",
    "                if x-target in m:\n",
    "                    return i-m[x-target]\n",
    "            return -1\n",
    "        s = sum(nums)\n",
    "        cnt = (target//s)*len(nums)\n",
    "        target %= s\n",
    "        ans = inf\n",
    "        m = {0:-1}\n",
    "        for i,x in enumerate(pre):\n",
    "            if x not in m:\n",
    "                m[x] = i\n",
    "            if x-target in m:\n",
    "                ans = min(ans,(i-m[x-target])+cnt)\n",
    "        target = s-target\n",
    "        m = {0:-1}\n",
    "        for i,x in enumerate(pre):\n",
    "            if x not in m:\n",
    "                m[x] = i\n",
    "            if x-target in m:\n",
    "                ans = min(ans,n-(i-m[x-target])+cnt)\n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, a: List[int], t: int) -> int:\n",
    "        n = len(a)\n",
    "        s = sum(a)\n",
    "        if t % s == 0:\n",
    "            return t // s * n\n",
    "        m = t // s\n",
    "        t %= s\n",
    "        k = 0\n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            k += a[i]\n",
    "            mp[k] = i\n",
    "        print(mp)\n",
    "        ans = -1\n",
    "        k = 0\n",
    "        for i in range(n):\n",
    "            if (t + k) in mp:\n",
    "                if ans == -1 or ans > mp[t + k] - i + 1:\n",
    "                    ans = mp[t + k] - i + 1\n",
    "            elif (t + k - s) in mp:\n",
    "                if ans == -1 or ans > mp[t + k - s] - i + 1 + n:\n",
    "                    ans = mp[t + k - s] - i + 1 + n\n",
    "            k += a[i]\n",
    "        if ans != -1:\n",
    "            ans += m * n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    " \n",
    "# test_sl = SortedList([3,5,1,2,7,6,4])\n",
    " \n",
    "# print(test_sl)\n",
    "\n",
    "# test_sl.add(2) #添加元素\n",
    "\n",
    "# test_sl.remove(4) #删除元素 元素不存在时会报错\n",
    "# test_sl.discard(1) #删除元素 元素不存在时不会报错\n",
    "\n",
    "# test_sl.pop() #移除最后一个元素\n",
    "\n",
    "# pos_left = test_sl.bisect_left(2) #查找元素存在的位置\n",
    "# pos_right = test_sl.bisect_right(2)\n",
    "# print(pos_left, pos_right)\n",
    " \n",
    "# nums = test_sl.count(2) #计数\n",
    "# print(nums)\n",
    " \n",
    "# ind = test_sl.index(2) #返回第一次出现的下标\n",
    "# print(ind)\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        if target % s == 0:\n",
    "            return target // s * len(nums)\n",
    "        n = len(nums)\n",
    "        sr = nums[:]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i != n - 1:\n",
    "                sr[i] += sr[i + 1]\n",
    "        vi = {0:-1}\n",
    "        res = -1\n",
    "        addv = 0\n",
    "        for i in range(n):\n",
    "            addv += nums[i]\n",
    "            vi[addv] = i\n",
    "\n",
    "        for i in range(n):\n",
    "            dis = n - i\n",
    "            val = target - sr[i]\n",
    "            dis += val // s * n\n",
    "            val %= s\n",
    "            if val in vi:\n",
    "                dis += vi[val] + 1\n",
    "                if res == -1 or res > dis:\n",
    "                    res = dis\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        # 制作pre数组\n",
    "        pre = [0]\n",
    "        base = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            pre.append(base)\n",
    "            base += nums[i]\n",
    "        pre.append(base)\n",
    "\n",
    "        d = {}\n",
    "        for i in range(len(pre)):\n",
    "            d[pre[i]] = i\n",
    "\n",
    "        print(d)\n",
    "\n",
    "        flag = False\n",
    "        res = 10 ** 9\n",
    "        for i in range(len(pre)):\n",
    "            self_mubiao = pre[i] + target  # 6\n",
    "\n",
    "            # 求9的位置\n",
    "            k = (self_mubiao // base)\n",
    "            tmp = self_mubiao - k * base  # 1\n",
    "            # print(tmp)\n",
    "            if d.get(tmp) is not None:\n",
    "                flag = True\n",
    "                res = min(res, d[tmp] + k * len(nums) - i)\n",
    "\n",
    "        # print(flag)\n",
    "        if not flag:\n",
    "            return -1\n",
    "        else:\n",
    "            return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        mul = len(nums)\n",
    "        a = [0]\n",
    "        for x in nums: a.append(x)\n",
    "        for x in nums: a.append(x)\n",
    "        n = len(a)\n",
    "        for i in range(1, n):\n",
    "            a[i] += a[i - 1]\n",
    "        d = defaultdict(int)\n",
    "        d[0] = 0\n",
    "        mod = target % s\n",
    "        ret, inf = 10**9, 10**9\n",
    "        for i in range(1, n):\n",
    "            now = a[i] % s\n",
    "            #now - p = mod\n",
    "            #p = mod - now\n",
    "            p = ((now - mod) % s + s) % s\n",
    "            # print(a[i], now, p)\n",
    "            if p in d and a[i] - a[d[p]] <= target:\n",
    "                ret = min(ret, i - d[p] + ((target - (a[i] - a[d[p]])) // s) * mul )\n",
    "            \n",
    "            d[now] = i\n",
    "        if ret == inf: ret = -1\n",
    "        return ret\n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        son = sum(nums)\n",
    "        n = len(nums)\n",
    "        k = target // son\n",
    "        r = target % son\n",
    "        slst = [0]\n",
    "        for i in range(2 * n):\n",
    "            slst.append(nums[i % n] + slst[-1])\n",
    "        rlst = [r + x for x in slst]\n",
    "        minl = n + 1\n",
    "        i, j = 0, 0\n",
    "        while j < 2 * n:\n",
    "            if slst[j] == rlst[i]:\n",
    "                minl = min(minl, abs(j - i))\n",
    "                j += 1\n",
    "                i += 1\n",
    "            elif slst[j] > rlst[i]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        if minl == n + 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return minl + n * k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        if target >= s: ans = (target//s) * n\n",
    "        else: ans = 0\n",
    "        t = target % s\n",
    "        # print(s,t)\n",
    "        if t == 0: return ans\n",
    "        t1 = s-t\n",
    "        l = n\n",
    "        acc = 0\n",
    "        acc_di = defaultdict(list)\n",
    "        acc_di[0] = [-1]\n",
    "        for i,x in enumerate(nums):\n",
    "            acc += x\n",
    "            if acc-t in acc_di:\n",
    "                l = min(l,i-acc_di[acc-t][-1])\n",
    "            if acc-t1 in acc_di:\n",
    "                l = min(l,n-i+acc_di[acc-t1][0])\n",
    "            acc_di[acc].append(i)\n",
    "        return ans + l if l!=n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        _sum = sum(nums)\n",
    "        n = len(nums)\n",
    "        ans = target // _sum * n\n",
    "        target %= _sum\n",
    "        pre = {0:[0,0]}\n",
    "        presum = 0\n",
    "        for i in range(n):\n",
    "            presum += nums[i]\n",
    "            if presum not in pre:\n",
    "                #[min prefix len, max prefix len]\n",
    "                pre[presum] = [i+1,i+1]\n",
    "            else:\n",
    "                pre[presum][1] = i+1\n",
    "\n",
    "        sufsum = 0\n",
    "        cur_ans = float('inf')\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            sufsum += num\n",
    "            if target - sufsum in pre:\n",
    "                cur_ans = min(cur_ans, pre[target - sufsum][0]+(n-i))\n",
    "            if _sum-target-sufsum in pre:\n",
    "                cur_ans = min(cur_ans, n-pre[_sum-target-sufsum][1]-(n-i))\n",
    "        ans += cur_ans\n",
    "        return ans if ans != float('inf') else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        pre[0] = nums[0]\n",
    "        suf = [0] * n\n",
    "        suf[n - 1] = nums[n - 1]\n",
    "        suf_map = {0: n, suf[n - 1]: n - 1}\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] + nums[i]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            suf[i] = suf[i + 1] + nums[i]\n",
    "            suf_map[suf[i]] = i\n",
    "        s = pre[n - 1]\n",
    "        ans = inf\n",
    "        for i, p in enumerate(pre):\n",
    "            last = (target - p) % s\n",
    "            t = (target - p) // s\n",
    "            if last in suf_map:\n",
    "                ans = min(ans, t * n + n - suf_map[last] + i + 1)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        pres = [0]\n",
    "\n",
    "        for i in range(n):\n",
    "            pres.append(pres[-1] + nums[i])\n",
    "\n",
    "        numsum = pres[-1]\n",
    "\n",
    "        for i in range(n):\n",
    "            pres.append(pres[-1] + nums[i])\n",
    "\n",
    "        for i in range(n):\n",
    "            pres.append(pres[-1] + nums[i])\n",
    "\n",
    "        q, r = divmod(target, numsum)\n",
    "\n",
    "        print(pres, q, r, n)\n",
    "\n",
    "        ret = inf\n",
    "        if q < 2:\n",
    "            for i in range(n + 1):\n",
    "                t = target + pres[i]\n",
    "                j = bisect.bisect_left(pres, t, i + 1)\n",
    "                if j < n * 3  + 1 and pres[j] == t:\n",
    "                    print(i, j, j - i)\n",
    "                    ret = min(ret, j - i)\n",
    "\n",
    "        else:\n",
    "            for i in range(n + 1):\n",
    "                t = r + numsum + pres[i]\n",
    "                j = bisect.bisect_left(pres, t, i + 1)\n",
    "                if n <= j < n * 3 + 1 and pres[j] == t:\n",
    "                    ret = min(ret, j - i + (q - 1) * n)\n",
    "\n",
    "        return ret if ret != inf else -1\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        sumnum = sum(nums)\n",
    "        res = (target // sumnum) * n\n",
    "        target %= sumnum\n",
    "        if target == 0:\n",
    "            return res\n",
    "        prexi = [nums[0]]*n\n",
    "        dic = defaultdict(int)\n",
    "        dic[nums[0]] = 1\n",
    "        for i in range(1, n):\n",
    "            prexi[i] = nums[i] + prexi[i-1]\n",
    "            dic[prexi[i]] = i+1\n",
    "        ress = dic[target] if dic[target] else inf\n",
    "        target1 = target\n",
    "        for i in range(n):\n",
    "            target = target+nums[i]\n",
    "            if dic[target]:\n",
    "                ress = min(ress, dic[target]-i-1)\n",
    "            target1 = target1-nums[i]\n",
    "            if dic[sumnum - target1]:\n",
    "                ress = min(ress, n-dic[sumnum-target1]+i+1)\n",
    "        return -1 if ress == inf else res + ress\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        sum_n_2_idx = {}\n",
    "        idx_2_sum_n = [0]\n",
    "        s = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num\n",
    "            idx_2_sum_n.append(s)\n",
    "            if s not in sum_n_2_idx:\n",
    "                sum_n_2_idx[s] = [i]\n",
    "            else:\n",
    "                sum_n_2_idx[s].append(i)\n",
    "        min_len = math.inf\n",
    "        for start in range(len(nums)):\n",
    "            tgt = target + idx_2_sum_n[start]\n",
    "            if tgt in sum_n_2_idx and sum_n_2_idx[tgt][-1] >= start:\n",
    "                end = self.bin_search(start, sum_n_2_idx[tgt])\n",
    "                min_len = min(min_len, end - start + 1)\n",
    "            else:\n",
    "                tgt = target + idx_2_sum_n[start] - s\n",
    "                if tgt in sum_n_2_idx:\n",
    "                    end = sum_n_2_idx[tgt][0]\n",
    "                    min_len = min(min_len, len(nums) - start + end + 1)\n",
    "                else:\n",
    "                    remain = target % s\n",
    "                    if target // s > 0:\n",
    "                        if remain == 0:\n",
    "                            min_len = min(min_len, len(nums) * (target // s))\n",
    "                        else:\n",
    "                            tgt = remain + idx_2_sum_n[start]\n",
    "                            if tgt in sum_n_2_idx and sum_n_2_idx[tgt][-1] >= start:\n",
    "                                end = self.bin_search(start, sum_n_2_idx[tgt])\n",
    "                                min_len = min(min_len, end - start + 1 + len(nums) * (target // s))\n",
    "                            else:\n",
    "                                tgt = remain + idx_2_sum_n[start] - s\n",
    "                                if tgt in sum_n_2_idx:\n",
    "                                    end = sum_n_2_idx[tgt][0]\n",
    "                                    min_len = min(min_len, len(nums) - start + end + 1 + len(nums) * (target // s))\n",
    "        if min_len == math.inf:\n",
    "            return -1\n",
    "        return min_len\n",
    "\n",
    "    def bin_search(self, target, lst):\n",
    "        low, high = 0, len(lst) - 1\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if lst[mid] < target:\n",
    "                low = mid + 1\n",
    "            elif lst[mid] > target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return lst[mid]\n",
    "        return lst[high]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        sum_n_2_idx = {}\n",
    "        idx_2_sum_n = [0]\n",
    "        s = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num\n",
    "            idx_2_sum_n.append(s)\n",
    "            if s not in sum_n_2_idx:\n",
    "                sum_n_2_idx[s] = [i]\n",
    "            else:\n",
    "                sum_n_2_idx[s].append(i)\n",
    "        min_len = math.inf\n",
    "        for start in range(len(nums)):\n",
    "            tgt = target + idx_2_sum_n[start]\n",
    "            if tgt in sum_n_2_idx and sum_n_2_idx[tgt][-1] >= start:\n",
    "                end = self.bin_search(start, sum_n_2_idx[tgt])\n",
    "                min_len = min(min_len, end - start + 1)\n",
    "            else:\n",
    "                tgt = target + idx_2_sum_n[start] - s\n",
    "                if tgt in sum_n_2_idx:\n",
    "                    end = sum_n_2_idx[tgt][0]\n",
    "                    min_len = min(min_len, len(nums) - start + end + 1)\n",
    "                elif min_len > len(nums):\n",
    "                    remain = target % s\n",
    "                    if target // s > 0:\n",
    "                        if remain == 0:\n",
    "                            min_len = min(min_len, len(nums) * (target // s))\n",
    "                        else:\n",
    "                            tgt = remain + idx_2_sum_n[start]\n",
    "                            if tgt in sum_n_2_idx and sum_n_2_idx[tgt][-1] >= start:\n",
    "                                end = self.bin_search(start, sum_n_2_idx[tgt])\n",
    "                                min_len = min(min_len, end - start + 1 + len(nums) * (target // s))\n",
    "                            else:\n",
    "                                tgt = remain + idx_2_sum_n[start] - s\n",
    "                                if tgt in sum_n_2_idx:\n",
    "                                    end = sum_n_2_idx[tgt][0]\n",
    "                                    min_len = min(min_len, len(nums) - start + end + 1 + len(nums) * (target // s))\n",
    "        if min_len == math.inf:\n",
    "            return -1\n",
    "        return min_len\n",
    "\n",
    "    def bin_search(self, target, lst):\n",
    "        low, high = 0, len(lst) - 1\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if lst[mid] < target:\n",
    "                low = mid + 1\n",
    "            elif lst[mid] > target:\n",
    "                high = mid\n",
    "            else:\n",
    "                return lst[mid]\n",
    "        return lst[high]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        res=0x3f3f3f3f\n",
    "        s0=sum(nums)\n",
    "        print(s0)\n",
    "        res1=target//s0\n",
    "        target-=res1*s0\n",
    "        d=dict()\n",
    "        s=0\n",
    "        d[0]=-1\n",
    "        if target==0:\n",
    "            return len(nums)*res1\n",
    "        for i in range(len(nums)):\n",
    "            s+=nums[i]\n",
    "            if s-target in d:\n",
    "                res=min(res,i-d[s-target])\n",
    "            d[s]=i\n",
    "        for i in range(len(nums)):\n",
    "            s+=nums[i]\n",
    "            if s-target in d:\n",
    "                res=min(res,i+len(nums)-d[s-target])\n",
    "            d[s]=i\n",
    "        return -1 if res==0x3f3f3f3f else res+res1*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        ans = len(nums) * (target // total)\n",
    "        target %= total\n",
    "        if target == 0:\n",
    "            return ans\n",
    "        res = inf\n",
    "        ref = {}\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            nums.append(nums[i])\n",
    "        for i in range(len(nums)):\n",
    "            t += nums[i]\n",
    "            if t - target in ref:\n",
    "                res = min(res, i + 1 - ref[t - target])\n",
    "            ref[t] = i + 1\n",
    "        if res == inf:\n",
    "            return -1\n",
    "        return res + ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, a: List[int], tar: int) -> int:\n",
    "        all_s = sum(a)\n",
    "        n = len(a)\n",
    "        if tar == all_s:\n",
    "            return n\n",
    "        \n",
    "        tem = 0\n",
    "        tem = tar // all_s\n",
    "        tar %= all_s\n",
    "            \n",
    "        if tar == 0:\n",
    "            return tem * n\n",
    "        \n",
    "        a = a + a\n",
    "        n *= 2\n",
    "        \n",
    "        st = {a[0] : 0}\n",
    "        curs = a[0]\n",
    "        res = 2 * n\n",
    "        has = False\n",
    "        for i in range(1, n):\n",
    "            curs += a[i]\n",
    "            if curs - tar in st:\n",
    "                has = True\n",
    "                res = min(i - st[curs - tar], res)\n",
    "            st[curs] = i\n",
    "        \n",
    "        return res + tem * n // 2 if has else -1\n",
    "            \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 后缀 + 完整 * k + 前缀\n",
    "        # 一个遍历完放哈希，一个一边遍历一边判断\n",
    "        tot = sum(nums)\n",
    "        if target in nums:\n",
    "            return 1\n",
    "        # 后缀\n",
    "        s = 0\n",
    "        post = defaultdict(lambda: -1) # 和 -》 位置\n",
    "        post[0] = n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += nums[i]\n",
    "            post[s] = i\n",
    "        pre = 0\n",
    "        ans = inf\n",
    "        # 不跨越\n",
    "        tmp = defaultdict(lambda: -1)\n",
    "        tmp[0] = -1\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - target >= 0 and tmp[pre - target] != -1:\n",
    "                idx = tmp[pre - target]\n",
    "                ans = min(ans, i - idx)\n",
    "                #print(ans, i, idx, pre)\n",
    "            tmp[pre] = i\n",
    "\n",
    "        #print(ans)\n",
    "\n",
    "        pre = 0\n",
    "        # 后缀 + 完整 * k + 前缀\n",
    "        for i in range(n + 1):\n",
    "            if target >= pre:\n",
    "                rest = target - pre\n",
    "                if post[rest % tot] != -1:\n",
    "                    repeat = rest // tot\n",
    "                    idx = post[rest % tot]\n",
    "                    ans = min(ans, repeat * n + (n - idx) + i)\n",
    "            if i >= n:\n",
    "                break\n",
    "            pre += nums[i]\n",
    "        return ans if ans != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        x, y = divmod(target, s)\n",
    "        if y == 0:\n",
    "            return x * n\n",
    "\n",
    "        cnt = Counter()\n",
    "        pre_sum = [0] * (2 * n + 1)\n",
    "        cnt[0] = -1\n",
    "        ans = float('inf')\n",
    "        nn = nums + nums\n",
    "        for i in range(2 * n):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nn[i]\n",
    "            diff = pre_sum[i + 1] - y\n",
    "            if diff in cnt and i - cnt[diff] <= n:\n",
    "                ans = min(ans, i - cnt[diff])\n",
    "                # print(i, cnt[diff])\n",
    "            cnt[pre_sum[i + 1]] = i\n",
    "\n",
    "        ans = x * n + ans\n",
    "        return ans if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        ans = inf \n",
    "        n = len(nums)\n",
    "        s = sum(nums) \n",
    "        pre = target  //s\n",
    "        post =   target % s\n",
    "        if post ==0: return n * pre\n",
    "        #print(pre,post)\n",
    "        pres,posts = 0 ,0\n",
    "        nn = nums \n",
    "        p,pd = {} , {} \n",
    "        for i in range( n):\n",
    "            pres+=nn[i]\n",
    "            posts+=nn[n-1-i]\n",
    "            if (pres == post or posts == post):\n",
    "                ans  = min (ans, pre * n + i + 1)\n",
    "            p[pres] = i \n",
    "            pd[posts] = n-1-i\n",
    "        for k in p:\n",
    "          \n",
    "         \n",
    "            if post - k  in  pd:\n",
    "                ans = min (ans, pre * n  + p[k] + 1  + n - pd[post - k])\n",
    "            if  (s - post) - k in  pd:\n",
    "                ans = min (ans, pre * n  + n - (p[k] + 1  + n - pd[(s - post) - k]))\n",
    "                \n",
    "            \n",
    "        \n",
    "        if ans==inf: return-1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        tot = sum(nums)\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums + nums))\n",
    "        ans = target // tot * n \n",
    "        target = target % tot\n",
    "        if target == 0:\n",
    "            return ans\n",
    "        cnt = Counter()\n",
    "        cnt[0] = -1\n",
    "        res = inf\n",
    "        for i, x in enumerate(s):\n",
    "            if (x - target) in cnt:\n",
    "                res = min(res, i - cnt[x - target])\n",
    "            cnt[x] = i\n",
    "        # print(cnt)\n",
    "        return ans + res if res < inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        nums=nums+nums\n",
    "        n=len(nums)\n",
    "        qzh=[nums[0]]+[0]*(n-1)\n",
    "        for i in range(1,n):qzh[i]=qzh[i-1]+nums[i]\n",
    "        nt=target%(qzh[-1]//2)\n",
    "        t={}\n",
    "        rr=999999999\n",
    "        # print(nums)\n",
    "        # print(qzh)\n",
    "        for i in range(n):\n",
    "            tt=qzh[i]-nt\n",
    "            if tt in t:rr=min(rr,i-t[tt])\n",
    "            t[qzh[i]]=i\n",
    "            # print(i,nt,rr,tt,t)\n",
    "        if rr==999999999 and nt==0:rr=0\n",
    "        return -1 if rr==999999999 else rr+(n//2)*(target//(qzh[-1]//2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        tot = sum(nums)\n",
    "        ans = 0\n",
    "        if target >= tot:\n",
    "            ans += target // tot * n\n",
    "            target %= tot\n",
    "        if target == 0: return ans\n",
    "        nums = nums[::] + nums[::]\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        print(s)\n",
    "        pos = {}\n",
    "        res = inf\n",
    "        for i in range(1, n * 2 + 1):\n",
    "            x = s[i] - target\n",
    "            if x in pos:\n",
    "                res = min(res, i - pos[x])\n",
    "            pos[s[i]] = i\n",
    "        return ans + res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSizeSubarray(self, nums: List[int], target: int) -> int:\n",
    "        #如果是nums+nums就简单了\n",
    "        def get(aa,target):\n",
    "            left = defaultdict(int)\n",
    "            cur = 0\n",
    "            left[0] = -1\n",
    "            ans = inf\n",
    "            for i in range(len(aa)):\n",
    "                cur+=aa[i]\n",
    "                left[cur] = i\n",
    "                if cur - target in left:\n",
    "                    ans = min(ans,i-left[cur-target])\n",
    "            return ans\n",
    "        aa = nums+nums\n",
    "        tot = sum(nums)\n",
    "        ans = get(aa,target)\n",
    "        mod = target%sum(nums)\n",
    "        if mod == 0:return min(ans,target//tot*len(nums))\n",
    "        ans = min(ans,get(aa,mod)+target//tot*len(nums))\n",
    "        if ans == inf:return -1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
